{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Regions Cut By Slashes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #hash-table #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #哈希表 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: regionsBySlashes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #由斜杠划分区域"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在由 <code>1 x 1</code> 方格组成的 <code>n&nbsp;x n</code>&nbsp;网格&nbsp;<code>grid</code> 中，每个 <code>1 x 1</code>&nbsp;方块由 <code>'/'</code>、<code>'\\'</code> 或空格构成。这些字符会将方块划分为一些共边的区域。</p>\n",
    "\n",
    "<p>给定网格&nbsp;<code>grid</code>&nbsp;表示为一个字符串数组，返回 <em>区域的数量</em> 。</p>\n",
    "\n",
    "<p>请注意，反斜杠字符是转义的，因此&nbsp;<code>'\\'</code> 用 <code>'\\\\'</code>&nbsp;表示。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/12/15/1.png\" style=\"height: 200px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [\" /\",\"/ \"]\n",
    "<strong>输出：</strong>2</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/12/15/2.png\" style=\"height: 198px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [\" /\",\"  \"]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2018/12/15/4.png\" style=\"height: 200px; width: 200px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [\"/\\\\\",\"\\\\/\"]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>回想一下，因为 \\ 字符是转义的，所以 \"/\\\\\" 表示 /\\，而 \"\\\\/\" 表示 \\/。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 30</code></li>\n",
    "\t<li><code>grid[i][j]</code> 是&nbsp;<code>'/'</code>、<code>'\\'</code>、或&nbsp;<code>' '</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [regions-cut-by-slashes](https://leetcode.cn/problems/regions-cut-by-slashes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [regions-cut-by-slashes](https://leetcode.cn/problems/regions-cut-by-slashes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\" /\",\"/ \"]', '[\" /\",\"  \"]', '[\"/\\\\\\\\\",\"\\\\\\\\/\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        uf = UF(n * n * 2)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                left = 2 * i * n + 2 * j\n",
    "            \n",
    "                if j < n - 1:\n",
    "                    uf.union(left+1, left+2)\n",
    "                \n",
    "                if grid[i][j] == ' ':\n",
    "                    uf.union(left, left+1)\n",
    "                \n",
    "                x = left + (1 if grid[i][j] == '/' else 0)\n",
    "                    \n",
    "                \n",
    "                if i < n - 1:\n",
    "                    uf.union(x, left + 2 * n + (1 if grid[i+1][j] == '\\\\' else 0))\n",
    "        \n",
    "        # for i in range(n-1):\n",
    "        #     left, right = (2 * i + 1) * n - 2, (2 * i + 1) * n - 1\n",
    "        #     if grid[i][j] == ' ':\n",
    "        #             uf.union(left, right)\n",
    "        #     if grid[i][j] == '/':\n",
    "        #         uf.union(right, left + 2 * n + (1 if grid[i+1][j] == '\\\\' else 0))\n",
    "        #     else:\n",
    "        #         uf.union(left, left + 2 * n + (1 if grid[i+1][j] == '\\\\' else 0))\n",
    "\n",
    "        # for j in range(n-1):\n",
    "        #     left, right = 2 * (n-1) * n + 2 * j, 2 * (n-1) * n + 2 * j + 1\n",
    "        #     uf.union(right, right+1)\n",
    "        #     if grid[i][j] == ' ':\n",
    "        #         uf.union(left, right)\n",
    "        \n",
    "        # if grid[n-1][n-1] == ' ':\n",
    "        #     uf.union(2 * n * n - 2, 2 * n * n - 1)\n",
    "        \n",
    "        return uf.cnt\n",
    "                \n",
    "\n",
    "class UF:\n",
    "    def __init__(self, N):\n",
    "        self.parent = list(range(N))\n",
    "        self.cnt = N\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.parent[x]:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx == ry:\n",
    "            return\n",
    "        self.parent[rx] = ry\n",
    "        self.cnt -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [i for i in range(n)]\n",
    "\n",
    "    def find(self, n: int) -> int:\n",
    "        while self.parent[n] != n:\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = self.parent[n]\n",
    "        return n\n",
    "    \n",
    "    def union(self, i: int, j: int):\n",
    "        pi = self.find(i)\n",
    "        pj = self.find(j)\n",
    "        if pi == pj:\n",
    "            return\n",
    "        self.parent[pi] = self.parent[pj]\n",
    "    \n",
    "    def count(self) -> int:\n",
    "        return len([i for i in range(len(self.parent)) if self.parent[i] == i])\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        N = n * 4\n",
    "        uf = UF(N * n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                base = (i * n + j) * 4\n",
    "                if grid[i][j] == '/':\n",
    "                    uf.union(base, base + 1)\n",
    "                    uf.union(base + 2, base + 3)\n",
    "                elif grid[i][j] == '\\\\':\n",
    "                    uf.union(base, base + 3)\n",
    "                    uf.union(base + 1, base + 2)                   \n",
    "                else:\n",
    "                    uf.union(base, base + 1)\n",
    "                    uf.union(base + 1, base + 2)\n",
    "                    uf.union(base + 2, base + 3)\n",
    "                if i > 0:\n",
    "                    uf.union(base + 1, base - 4 * n + 3)\n",
    "                if j > 0:\n",
    "                    uf.union(base, base - 2)\n",
    "        return uf.count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union:\n",
    "    def __init__(self, num: int) -> None:\n",
    "        self.parent = list(range(num))\n",
    "        self.rank = [0] * num\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def merge(self, x: int, y: int) -> None:\n",
    "        px = self.find(x)\n",
    "        py = self.find(y)\n",
    "        if px == py:\n",
    "            return\n",
    "        if self.rank[px] > self.rank[py]:\n",
    "            self.parent[py] = self.parent[px]\n",
    "        elif self.rank[px] < self.rank[py]:\n",
    "            self.parent[px] = self.parent[py]\n",
    "        else:\n",
    "            self.parent[py] = self.parent[px]\n",
    "            self.rank[px] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        un = Union(4 * n * n)\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                index = 4 * (r * n + c)\n",
    "                if grid[r][c] == \"/\":\n",
    "                    un.merge(index + 0, index + 3)\n",
    "                    un.merge(index + 1, index + 2)\n",
    "                elif grid[r][c] == \"\\\\\":\n",
    "                    un.merge(index + 0, index + 1)\n",
    "                    un.merge(index + 2, index + 3)\n",
    "                elif grid[r][c] == \" \":\n",
    "                    un.merge(index + 0, index + 1)\n",
    "                    un.merge(index + 1, index + 2)\n",
    "                    un.merge(index + 2, index + 3)\n",
    "                else:\n",
    "                    None\n",
    "                if c < n - 1:\n",
    "                    un.merge(index + 1, index + 4 + 3) \n",
    "                if r < n - 1:\n",
    "                    un.merge(index + 2, index + 4 * n + 0)  \n",
    "        ans = 0\n",
    "        for i in range(4 * n * n):\n",
    "            if un.find(i) == i:\n",
    "                ans += 1\n",
    "        return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self._count = n\n",
    "\n",
    "    def find(self, n: int) -> int:\n",
    "        while self.parent[n] != n:\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = self.parent[n]\n",
    "        return n\n",
    "    \n",
    "    def union(self, i: int, j: int):\n",
    "        pi = self.find(i)\n",
    "        pj = self.find(j)\n",
    "        if pi == pj:\n",
    "            return\n",
    "        self._count -= 1\n",
    "        self.parent[pi] = self.parent[pj]\n",
    "    \n",
    "    def count(self) -> int:\n",
    "        return self._count\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        N = n * 4\n",
    "        uf = UF(N * n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                base = (i * n + j) * 4\n",
    "                if grid[i][j] == '/':\n",
    "                    uf.union(base, base + 1)\n",
    "                    uf.union(base + 2, base + 3)\n",
    "                elif grid[i][j] == '\\\\':\n",
    "                    uf.union(base, base + 3)\n",
    "                    uf.union(base + 1, base + 2)                   \n",
    "                else:\n",
    "                    uf.union(base, base + 1)\n",
    "                    uf.union(base + 1, base + 2)\n",
    "                    uf.union(base + 2, base + 3)\n",
    "                if i > 0:\n",
    "                    uf.union(base + 1, base - 4 * n + 3)\n",
    "                if j > 0:\n",
    "                    uf.union(base, base - 2)\n",
    "        return uf.count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "        self.count = n \n",
    "\n",
    "    def find(self, n):\n",
    "        while n != self.parent[n]:\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = self.parent[n]\n",
    "        return n\n",
    "\n",
    "    def connected(self, n1, n2):\n",
    "        return self.find(n1) == self.find(n2)\n",
    "\n",
    "    def union(self, n1, n2):\n",
    "        if self.connected(n1, n2):\n",
    "            return\n",
    "        p1, p2 = self.find(n1), self.find(n2)\n",
    "        if self.rank[p1] > self.rank[p2]:\n",
    "            self.parent[p2] = p1\n",
    "            self.rank[p1] += self.rank[p2]\n",
    "        else:\n",
    "            self.parent[p1] = p2\n",
    "            self.rank[p2] += self.rank[p1]\n",
    "        self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        uf = UF(R * C * 4)\n",
    "        def pos(r, c, i):\n",
    "            return (r * C + c) * 4 + i\n",
    "        for r in range(R):\n",
    "            for c in range(C):\n",
    "                v = grid[r][c]\n",
    "                if r + 1 < R:\n",
    "                    uf.union(pos(r, c, 3), pos(r + 1, c, 1))\n",
    "                if c + 1 < C:\n",
    "                    uf.union(pos(r, c, 2), pos(r, c + 1, 0))\n",
    "                if v == '/':\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 1))\n",
    "                    uf.union(pos(r, c, 2), pos(r, c, 3))\n",
    "                if v == '\\\\':\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 3))\n",
    "                    uf.union(pos(r, c, 1), pos(r, c, 2))\n",
    "                if v == ' ':\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 1))\n",
    "                    uf.union(pos(r, c, 1), pos(r, c, 2))\n",
    "                    uf.union(pos(r, c, 2), pos(r, c, 3))\n",
    "\n",
    "        return uf.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.p = [i for i in range(n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        while self.p[x] != x:\n",
    "            x = self.p[x]\n",
    "        return x\n",
    "        \n",
    "    def union(self, x, y):\n",
    "        xr = self.find(x)\n",
    "        yr = self.find(y)\n",
    "        if xr == yr:\n",
    "            return\n",
    "\n",
    "        self.p[xr] = yr\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        uf = UF(4 * n * n)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                index = (i * n + j) * 4\n",
    "                if grid[i][j] == '/':\n",
    "                    uf.union(index+0, index+3)\n",
    "                    uf.union(index+1, index+2)\n",
    "                elif grid[i][j] == '\\\\':\n",
    "                    uf.union(index+0, index+1)\n",
    "                    uf.union(index+2, index+3)\n",
    "                else:\n",
    "                    uf.union(index+0, index+1)\n",
    "                    uf.union(index+1, index+2)\n",
    "                    uf.union(index+2, index+3)\n",
    "\n",
    "                if i + 1 < n:\n",
    "                    uf.union(index+2, index+n*4+0)\n",
    "                if j + 1 < n:\n",
    "                    uf.union(index+1, index+4+3)\n",
    "\n",
    "        return sum(1 for i in range(4*n*n) if uf.find(i) == i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        V = dict()\n",
    "        n = len(grid)\n",
    "        res = 1\n",
    "\n",
    "        def find(x):\n",
    "            while x!=V[x]:\n",
    "                x = V[x]\n",
    "            return x\n",
    "        \n",
    "        def merge(x, y):\n",
    "            V[find(x)] = find(y)\n",
    "        \n",
    "        for i in range(n+1):\n",
    "            V[(i, 0)] = V[(0, i)] = V[(n, i)] = V[(i, n)] = (0, 0)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n):\n",
    "                V[(i, j)] = (i, j)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]=='/':\n",
    "                    x, y = find((i+1, j)), find((i, j+1))\n",
    "                    if x==y:\n",
    "                        res+=1\n",
    "                    else:\n",
    "                        merge(x, y)\n",
    "                elif grid[i][j]=='\\\\':\n",
    "                    x, y = find((i, j)), find((i+1, j+1))\n",
    "                    if x==y:\n",
    "                        res+=1\n",
    "                    else:\n",
    "                        merge(x, y)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.count = n\n",
    "    \n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        self.parent[root_x] = root_y\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        union_find = UnionFind(4*n*n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                index = 4 * (i * n + j)\n",
    "                if grid[i][j] == ' ':\n",
    "                    union_find.union(index, index+1)\n",
    "                    union_find.union(index+1, index+2)\n",
    "                    union_find.union(index+2, index+3)\n",
    "                elif grid[i][j] == '/':\n",
    "                    union_find.union(index, index+1)\n",
    "                    union_find.union(index+2, index+3)\n",
    "                else:\n",
    "                    union_find.union(index, index+3)\n",
    "                    union_find.union(index+1, index+2)\n",
    "                if j < n - 1:\n",
    "                    union_find.union(index+2, index+4)\n",
    "                if i < n - 1:\n",
    "                    union_find.union(index+3, index+4*n+1)\n",
    "        return union_find.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m*n*4)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                w = grid[i][j]\n",
    "                x = i*n+j\n",
    "                if w == \"\\\\\":\n",
    "                    uf.union(4*x, 4*x+2)\n",
    "                    uf.union(4 * x+1, 4 * x + 3)\n",
    "                elif w == \"/\":\n",
    "                    uf.union(4 * x, 4 * x + 1)\n",
    "                    uf.union(4 * x + 2, 4 * x + 3)\n",
    "                else:\n",
    "                    uf.union(4 * x, 4 * x + 2)\n",
    "                    uf.union(4 * x + 1, 4 * x + 3)\n",
    "                    uf.union(4 * x, 4 * x + 1)\n",
    "                    uf.union(4 * x + 2, 4 * x + 3)\n",
    "                if j + 1 < n:\n",
    "                    y = i * n + j + 1\n",
    "                    uf.union(4 * x + 2, 4 * y + 1)\n",
    "                if i + 1 < m:\n",
    "                    y = (i + 1) * n + j\n",
    "                    uf.union(4 * x + 3, 4 * y)\n",
    "        return uf.part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "        self.count = n \n",
    "\n",
    "    def find(self, n):\n",
    "        while n != self.parent[n]:\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = self.parent[n]\n",
    "        return n\n",
    "\n",
    "    def connected(self, n1, n2):\n",
    "        return self.find(n1) == self.find(n2)\n",
    "\n",
    "    def union(self, n1, n2):\n",
    "        if self.connected(n1, n2):\n",
    "            return\n",
    "        p1, p2 = self.find(n1), self.find(n2)\n",
    "        if self.rank[p1] > self.rank[p2]:\n",
    "            self.parent[p2] = p1\n",
    "            self.rank[p1] += self.rank[p2]\n",
    "        else:\n",
    "            self.parent[p1] = p2\n",
    "            self.rank[p2] += self.rank[p1]\n",
    "        self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        uf = UF(R * C * 4)\n",
    "        def pos(r, c, i):\n",
    "            return (r * C + c) * 4 + i\n",
    "        for r in range(R):\n",
    "            for c in range(C):\n",
    "                v = grid[r][c]\n",
    "                if r + 1 < R:\n",
    "                    uf.union(pos(r, c, 3), pos(r + 1, c, 1))\n",
    "                if c + 1 < C:\n",
    "                    uf.union(pos(r, c, 2), pos(r, c + 1, 0))\n",
    "                if v == '/':\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 1))\n",
    "                    uf.union(pos(r, c, 2), pos(r, c, 3))\n",
    "                if v == '\\\\':\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 3))\n",
    "                    uf.union(pos(r, c, 1), pos(r, c, 2))\n",
    "                if v == ' ':\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 1))\n",
    "                    uf.union(pos(r, c, 1), pos(r, c, 2))\n",
    "                    uf.union(pos(r, c, 2), pos(r, c, 3))\n",
    "\n",
    "        return uf.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [1] * n\n",
    "        self.count = n \n",
    "\n",
    "    def find(self, n):\n",
    "        while n != self.parent[n]:\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = self.parent[n]\n",
    "        return n\n",
    "\n",
    "    def connected(self, n1, n2):\n",
    "        return self.find(n1) == self.find(n2)\n",
    "\n",
    "    def union(self, n1, n2):\n",
    "        if self.connected(n1, n2):\n",
    "            return\n",
    "        p1, p2 = self.find(n1), self.find(n2)\n",
    "        if self.rank[p1] > self.rank[p2]:\n",
    "            self.parent[p2] = p1\n",
    "            self.rank[p1] += self.rank[p2]\n",
    "        else:\n",
    "            self.parent[p1] = p2\n",
    "            self.rank[p2] += self.rank[p1]\n",
    "        self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid):\n",
    "        R, C = len(grid), len(grid[0])\n",
    "        uf = UF(R * C * 4)\n",
    "        def pos(r, c, i):\n",
    "            return (r * C + c) * 4 + i\n",
    "        for r in range(R):\n",
    "            for c in range(C):\n",
    "                v = grid[r][c]\n",
    "                if r + 1 < R: # connect to right\n",
    "                    uf.union(pos(r, c, 3), pos(r + 1, c, 1))\n",
    "                if c + 1 < C: # connect to bottom\n",
    "                    uf.union(pos(r, c, 2), pos(r, c + 1, 0))\n",
    "                if v == '/': # depend on encoding of 1, 2, 3, 4\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 1))\n",
    "                    uf.union(pos(r, c, 2), pos(r, c, 3))\n",
    "                if v == '\\\\': # escape '\\\\' means '\\'\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 3))\n",
    "                    uf.union(pos(r, c, 1), pos(r, c, 2))\n",
    "                if v == ' ': # connect all\n",
    "                    uf.union(pos(r, c, 0), pos(r, c, 1))\n",
    "                    uf.union(pos(r, c, 1), pos(r, c, 2))\n",
    "                    uf.union(pos(r, c, 2), pos(r, c, 3))\n",
    "        return uf.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        \"\"\"\n",
    "        1 <= n <= 30\n",
    "        \"\"\"\n",
    "        n = len(grid)\n",
    "        seen = set()\n",
    "\n",
    "        def find_neighbors(x, y, z):\n",
    "            dq = Deque([(x, y, z)])\n",
    "            while dq:\n",
    "                a, b, c = dq.popleft()\n",
    "                if (a, b, c) in seen or not 0 <= a < n or not 0<= b < n:\n",
    "                    continue\n",
    "                seen.add((a, b, c))\n",
    "                if c == 0:\n",
    "                    dq.append((a - 1, b, 2))\n",
    "                    if grid[a][b] != '\\\\':\n",
    "                        dq.append((a, b, 1))\n",
    "                    if grid[a][b] != '/':\n",
    "                        dq.append((a, b, 3))\n",
    "                elif c == 1:\n",
    "                    dq.append((a, b - 1, 3))\n",
    "                    if grid[a][b] != '/':\n",
    "                        dq.append((a, b, 2))\n",
    "                    if grid[a][b] != '\\\\':\n",
    "                        dq.append((a, b, 0))\n",
    "                elif c == 2:\n",
    "                    dq.append((a + 1, b, 0))\n",
    "                    if grid[a][b] != '/':\n",
    "                        dq.append((a, b, 1))\n",
    "                    if grid[a][b] != '\\\\':\n",
    "                        dq.append((a, b, 3))\n",
    "                else:\n",
    "                    dq.append((a, b + 1, 1))\n",
    "                    if grid[a][b] != '/':\n",
    "                        dq.append((a, b, 0))\n",
    "                    if grid[a][b] != '\\\\':\n",
    "                        dq.append((a, b, 2))\n",
    "\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(4):\n",
    "                    if (i, j, k) not in seen:\n",
    "                        find_neighbors(i, j, k)\n",
    "                        ret += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class UF:\n",
    "  def __init__(self, M):\n",
    "      self.parent = {}\n",
    "      self.cnt = 0\n",
    "      # 初始化 parent，size 和 cnt\n",
    "      for i in range(M):\n",
    "          self.parent[i] = i\n",
    "          self.cnt += 1\n",
    "\n",
    "  def find(self, x):\n",
    "      if x != self.parent[x]:\n",
    "          self.parent[x] = self.find(self.parent[x])\n",
    "          return self.parent[x]\n",
    "      return x\n",
    "  def union(self, p, q):\n",
    "      if self.connected(p, q): return\n",
    "      leader_p = self.find(p)\n",
    "      leader_q = self.find(q)\n",
    "      self.parent[leader_p] = leader_q\n",
    "      self.cnt -= 1\n",
    "  def connected(self, p, q):\n",
    "      return self.find(p) == self.find(q)\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid):\n",
    "        n = len(grid)\n",
    "        N = n * n * 4\n",
    "        uf = UF(N)\n",
    "        def get_pos(row, col, i):\n",
    "            return (row * n + col) * 4 + i\n",
    "        for row in range(n):\n",
    "            for col in range(n):\n",
    "                v = grid[row][col]\n",
    "                if row > 0:\n",
    "                    uf.union(get_pos(row - 1, col, 2), get_pos(row, col, 1))\n",
    "                if col > 0:\n",
    "                    uf.union(get_pos(row, col - 1, 3), get_pos(row, col, 0))\n",
    "                if v == '/':\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 1))\n",
    "                    uf.union(get_pos(row, col, 2), get_pos(row, col, 3))\n",
    "                if v == '\\\\':\n",
    "                    uf.union(get_pos(row, col, 1), get_pos(row, col, 3))\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 2))\n",
    "                if v == ' ':\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 1))\n",
    "                    uf.union(get_pos(row, col, 1), get_pos(row, col, 2))\n",
    "                    uf.union(get_pos(row, col, 2), get_pos(row, col, 3))\n",
    "\n",
    "        return uf.cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n,cnt=len(grid),0\n",
    "        fa=[i for i in range((n+1)*(n+1))]\n",
    "        for i in range(n+1):fa[i],fa[i*(n+1)],fa[n*(n+1)+i],fa[i*(n+1)+n]=0,0,0,0\n",
    "        def getfa(u):\n",
    "            nonlocal fa\n",
    "            fa[u]=(u if fa[u]==u else getfa(fa[u]))\n",
    "            return fa[u]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if(grid[i][j]=='/'):cnt+=1;fa[getfa(i*(n+1)+j+1)]=getfa((i+1)*(n+1)+j)\n",
    "                elif(grid[i][j]=='\\\\'):cnt+=1;fa[getfa((i+1)*(n+1)+j+1)]=getfa(i*(n+1)+j)\n",
    "        for i in range((n+1)*(n+1)):getfa(i)\n",
    "        return cnt+4*n-(n+1)*(n+1)+len(set(fa))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class UF:\n",
    "#     def __init__(self, M):\n",
    "#         self.parent = {}\n",
    "#         self.cnt = 0\n",
    "#         # 初始化 parent, size 和 cnt\n",
    "#         for i in range(M):\n",
    "#             self.parent[i] = i\n",
    "#             self.cnt += 1\n",
    "\n",
    "#     def find(self, x):\n",
    "#         if x != self.parent[x]:\n",
    "#             self.parent[x] = self.find(self.parent[x])\n",
    "#             return self.parent[x]\n",
    "#         return x\n",
    "\n",
    "#     def union(self, p, q):\n",
    "#         if self.connected(p, q):\n",
    "#             return\n",
    "#         leader_p = self.find(p)\n",
    "#         leader_q = self.find(q)\n",
    "#         self.parent[leader_p] = leader_q\n",
    "#         self.cnt -= 1\n",
    "\n",
    "#     def connected(self, p, q):\n",
    "#         return self.find(p) == self.find(q)\n",
    "        \n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "\n",
    "        # n = len(grid)\n",
    "        # p = list(range(n))\n",
    "        # size = [1] * n\n",
    "\n",
    "        # def find(x):\n",
    "        #     if x \n",
    "        n,cnt=len(grid),0\n",
    "        fa=[i for i in range((n+1)*(n+1))]\n",
    "        for i in range(n+1):fa[i],fa[i*(n+1)],fa[n*(n+1)+i],fa[i*(n+1)+n]=0,0,0,0\n",
    "        def getfa(u):\n",
    "            nonlocal fa\n",
    "            fa[u]=(u if fa[u]==u else getfa(fa[u]))\n",
    "            return fa[u]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if(grid[i][j]=='/'):cnt+=1;fa[getfa(i*(n+1)+j+1)]=getfa((i+1)*(n+1)+j)\n",
    "                elif(grid[i][j]=='\\\\'):cnt+=1;fa[getfa((i+1)*(n+1)+j+1)]=getfa(i*(n+1)+j)\n",
    "        for i in range((n+1)*(n+1)):getfa(i)\n",
    "        return cnt+4*n-(n+1)*(n+1)+len(set(fa))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "  def __init__(self, M):\n",
    "      self.parent = {}\n",
    "      self.cnt = 0\n",
    "      # 初始化 parent，size 和 cnt\n",
    "      for i in range(M):\n",
    "          self.parent[i] = i\n",
    "          self.cnt += 1\n",
    "\n",
    "  def find(self, x):\n",
    "      if x != self.parent[x]:\n",
    "          self.parent[x] = self.find(self.parent[x])\n",
    "          return self.parent[x]\n",
    "      return x\n",
    "  def union(self, p, q):\n",
    "      if self.connected(p, q): return\n",
    "      leader_p = self.find(p)\n",
    "      leader_q = self.find(q)\n",
    "      self.parent[leader_p] = leader_q\n",
    "      self.cnt -= 1\n",
    "  def connected(self, p, q):\n",
    "      return self.find(p) == self.find(q)\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid):\n",
    "        n = len(grid)\n",
    "        N = n * n * 4\n",
    "        uf = UF(N)\n",
    "        def get_pos(row, col, i):\n",
    "            return (row * n + col) * 4 + i\n",
    "        for row in range(n):\n",
    "            for col in range(n):\n",
    "                v = grid[row][col]\n",
    "                if row > 0:\n",
    "                    uf.union(get_pos(row - 1, col, 2), get_pos(row, col, 1))\n",
    "                if col > 0:\n",
    "                    uf.union(get_pos(row, col - 1, 3), get_pos(row, col, 0))\n",
    "                if v == '/':\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 1))\n",
    "                    uf.union(get_pos(row, col, 2), get_pos(row, col, 3))\n",
    "                if v == '\\\\':\n",
    "                    uf.union(get_pos(row, col, 1), get_pos(row, col, 3))\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 2))\n",
    "                if v == ' ':\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 1))\n",
    "                    uf.union(get_pos(row, col, 1), get_pos(row, col, 2))\n",
    "                    uf.union(get_pos(row, col, 2), get_pos(row, col, 3))\n",
    "\n",
    "        return uf.cnt\n",
    "\n",
    "\n",
    "# class UF:\n",
    "#     def __init__(self, M):\n",
    "#         self.parent = {}\n",
    "#         self.cnt = 0\n",
    "#         # 初始化 parent, size 和 cnt\n",
    "#         for i in range(M):\n",
    "#             self.parent[i] = i\n",
    "#             self.cnt += 1\n",
    "\n",
    "#     def find(self, x):\n",
    "#         if x != self.parent[x]:\n",
    "#             self.parent[x] = self.find(self.parent[x])\n",
    "#             return self.parent[x]\n",
    "#         return x\n",
    "\n",
    "#     def union(self, p, q):\n",
    "#         if self.connected(p, q): return\n",
    "#         leader_p = self.find(p)\n",
    "#         leader_q = self.find(q)\n",
    "#         self.parent[leader_p] = leader_q\n",
    "#         self.cnt -= 1\n",
    "\n",
    "#     def connected(self, p, q):\n",
    "#         return self.find(p) == self.find(q)\n",
    "        \n",
    "# class Solution:\n",
    "#     def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "\n",
    "#         n = len(grid)\n",
    "#         N = n * n * 4 # 将一个格子拆成 4个点\n",
    "#         uf = UF(N)\n",
    "        \n",
    "#         # 将二维的点映射到一维\n",
    "#         def get_pos(row, col, i):\n",
    "#             # i 指代将一个点分成的四个部分\n",
    "#             return (row * n + col) * 4 + i\n",
    "\n",
    "#         for row in range(n):\n",
    "#             for col in range(n):\n",
    "#                 v = grid[row][col]\n",
    "#                 if row > 0:\n",
    "#                     # 上一排和 2号 和下一排的 1号 肯定在一块区域里\n",
    "#                     uf.union(get_pos(row - 1, col, 2), get_pos(row, col, 1))\n",
    "#                 if col > 0:\n",
    "#                     # 左右相邻的 3号和 0号 肯定在一块区域里\n",
    "#                     uf.union(get_pos(row, col - 1, 3), get_pos(row, col, 0))\n",
    "#                 if v == '/': # 合并 0 1 号，2 3 号\n",
    "#                     uf.union(get_pos(row, col, 0), get_pos(row, col, 1))\n",
    "#                     uf.union(get_pos(row, col, 2), get_pos(row, col, 3))\n",
    "#                 if v == '\\\\': # 合并 0 2 号，1 3 号\n",
    "#                     uf.union(get_pos(row, col, 1), get_pos(row, col, 3))\n",
    "#                     uf.union(get_pos(row, col, 0), get_pos(row, col, 2))\n",
    "#                 if v == '': # 合并 0 1 2 3 号 四块区域\n",
    "#                     uf.union(get_pos(row, col, 0), get_pos(row, col, 1))\n",
    "#                     uf.union(get_pos(row, col, 1), get_pos(row, col, 2))\n",
    "#                     uf.union(get_pos(row, col, 2), get_pos(row, col, 3))\n",
    "\n",
    "#         return uf.cnt\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # p = list(range(n))\n",
    "        # size = [1] * n\n",
    "\n",
    "        # def find(x):\n",
    "        #     if p[x] != x:\n",
    "        #         p[x] = find(p[x]) \n",
    "        #     return p[x]\n",
    "\n",
    "        # def is_same(a, b):\n",
    "        #     pa, pb = find(a), find(b)\n",
    "        #     return True if pa == pb else False\n",
    "\n",
    "        # def union(a, b):\n",
    "        #     if is_same(a, b):\n",
    "        #         return\n",
    "        #     p[pa] = pb\n",
    "        #     size[pb] += size[pa]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n,cnt=len(grid),0\n",
    "        # fa=[i for i in range((n+1)*(n+1))]\n",
    "        # for i in range(n+1):fa[i],fa[i*(n+1)],fa[n*(n+1)+i],fa[i*(n+1)+n]=0,0,0,0\n",
    "        # def getfa(u):\n",
    "        #     nonlocal fa\n",
    "        #     fa[u]=(u if fa[u]==u else getfa(fa[u]))\n",
    "        #     return fa[u]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if(grid[i][j]=='/'):cnt+=1;fa[getfa(i*(n+1)+j+1)]=getfa((i+1)*(n+1)+j)\n",
    "        #         elif(grid[i][j]=='\\\\'):cnt+=1;fa[getfa((i+1)*(n+1)+j+1)]=getfa(i*(n+1)+j)\n",
    "        # for i in range((n+1)*(n+1)):getfa(i)\n",
    "        # return cnt+4*n-(n+1)*(n+1)+len(set(fa))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class UF:\n",
    "  def __init__(self, M):\n",
    "      self.parent = {}\n",
    "      self.cnt = 0\n",
    "      # 初始化 parent，size 和 cnt\n",
    "      for i in range(M):\n",
    "          self.parent[i] = i\n",
    "          self.cnt += 1\n",
    "\n",
    "  def find(self, x):\n",
    "      if x != self.parent[x]:\n",
    "          self.parent[x] = self.find(self.parent[x])\n",
    "          return self.parent[x]\n",
    "      return x\n",
    "  def union(self, p, q):\n",
    "      if self.connected(p, q): return\n",
    "      leader_p = self.find(p)\n",
    "      leader_q = self.find(q)\n",
    "      self.parent[leader_p] = leader_q\n",
    "      self.cnt -= 1\n",
    "  def connected(self, p, q):\n",
    "      return self.find(p) == self.find(q)\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid):\n",
    "        n = len(grid)\n",
    "        N = n * n * 4\n",
    "        uf = UF(N)\n",
    "        def get_pos(row, col, i):\n",
    "            return (row * n + col) * 4 + i\n",
    "        for row in range(n):\n",
    "            for col in range(n):\n",
    "                v = grid[row][col]\n",
    "                if row > 0:\n",
    "                    uf.union(get_pos(row - 1, col, 2), get_pos(row, col, 1))\n",
    "                if col > 0:\n",
    "                    uf.union(get_pos(row, col - 1, 3), get_pos(row, col, 0))\n",
    "                if v == '/':\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 1))\n",
    "                    uf.union(get_pos(row, col, 2), get_pos(row, col, 3))\n",
    "                if v == '\\\\':\n",
    "                    uf.union(get_pos(row, col, 1), get_pos(row, col, 3))\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 2))\n",
    "                if v == ' ':\n",
    "                    uf.union(get_pos(row, col, 0), get_pos(row, col, 1))\n",
    "                    uf.union(get_pos(row, col, 1), get_pos(row, col, 2))\n",
    "                    uf.union(get_pos(row, col, 2), get_pos(row, col, 3))\n",
    "\n",
    "        return uf.cnt\n",
    "\n",
    "# 作者：lucifer\n",
    "# 链接：https://leetcode.cn/problems/regions-cut-by-slashes/solutions/575381/liang-chong-fang-fa-bing-cha-ji-he-dfs95-uhof/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        size = len(grid)\n",
    "        Node_num = size + 1\n",
    "        self.res = 1\n",
    "\n",
    "        dad = [i for i in range(Node_num * Node_num + 1)]\n",
    "\n",
    "        def find(x):\n",
    "            if dad[x] != x:\n",
    "                dad[x] = find(dad[x])\n",
    "            return dad[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            fx = find(x)\n",
    "            fy = find(y)\n",
    "            if fx != fy:\n",
    "                dad[fx] = fy\n",
    "            else:\n",
    "                self.res += 1\n",
    "\n",
    "        for i in range(Node_num * Node_num):\n",
    "            if i % Node_num == 0 or i % Node_num == Node_num - 1 or i // Node_num == 0 or i // Node_num == Node_num - 1:\n",
    "                union(i, Node_num * Node_num)\n",
    "        \n",
    "        for i in range(size):\n",
    "            for j in range(size):\n",
    "                if grid[i][j] ==  '/' :\n",
    "                    union(Node_num * i + j + 1, Node_num * (i + 1) + j)\n",
    "                elif grid[i][j] == '\\\\':\n",
    "                    union(Node_num * i + j, Node_num * (i + 1) + j + 1)\n",
    "        \n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet():\n",
    "        def __init__(self):\n",
    "            self.setSize = 0  #不连通区域\n",
    "            self.father = {}\n",
    "            \n",
    "        def add(self,x):  #添加根节点\n",
    "            if x not in self.father:\n",
    "                self.father[x] = -1\n",
    "                self.setSize += 1\n",
    "\n",
    "        def find(self,x):\n",
    "            root = x\n",
    "            while self.father[root] != -1:  #找根节点\n",
    "                root = self.father[root]\n",
    "\n",
    "            while (x != root): #路径压缩\n",
    "                o = self.father[x]  #找x的父节点\n",
    "                self.father[x] = root  #把x的父节点设置成刚才找到的根\n",
    "                x = o  #往上一层\n",
    "\n",
    "            return root\n",
    "\n",
    "        def merge(self,x, y):\n",
    "            root_x = self.find(x)\n",
    "            root_y = self.find(y)\n",
    "            if root_x != root_y:\n",
    "                self.father[root_x] = root_y  #合并\n",
    "                self.setSize -= 1\n",
    "                \n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        uf = UnionFindSet()\n",
    "        lenth = len(grid)\n",
    "        for row in range(lenth):\n",
    "            for col in range(lenth):\n",
    "                char = grid[row][col]\n",
    "                if char == ' ':\n",
    "                    uf.add((row, col, 0))\n",
    "                    uf.add((row, col, 1))\n",
    "                    uf.add((row, col, 2))\n",
    "                    uf.add((row, col, 3))\n",
    "                    uf.merge((row, col, 0),(row, col, 1))\n",
    "                    uf.merge((row, col, 0),(row, col, 2))\n",
    "                    uf.merge((row, col, 0),(row, col, 3))\n",
    "                elif char == '\\\\':\n",
    "                    uf.add((row, col, 0))\n",
    "                    uf.add((row, col, 1))\n",
    "                    uf.add((row, col, 2))\n",
    "                    uf.add((row, col, 3))\n",
    "                    uf.merge((row, col, 0),(row, col, 1))\n",
    "                    uf.merge((row, col, 2),(row, col, 3))\n",
    "                elif char == '/':\n",
    "                    uf.add((row, col, 0))\n",
    "                    uf.add((row, col, 1))\n",
    "                    uf.add((row, col, 2))\n",
    "                    uf.add((row, col, 3))\n",
    "                    uf.merge((row, col, 0),(row, col, 3))\n",
    "                    uf.merge((row, col, 1),(row, col, 2))\n",
    "                \n",
    "                if row < lenth: #连接下面的块\n",
    "                    uf.add((row + 1, col, 0))\n",
    "                    uf.merge((row, col, 2),(row + 1, col, 0))\n",
    "                if col < lenth:  #连接右面的块\n",
    "                    uf.add((row, col + 1, 3))\n",
    "                    uf.merge((row, col, 1),(row, col + 1, 3))\n",
    "\n",
    "        return uf.setSize\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        N = n * n * 4\n",
    "        ans = 0\n",
    "        fa = list(range(N))\n",
    "        def find(x):\n",
    "            #print(x)\n",
    "            if fa[x] != x: fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a, b):\n",
    "            pa, pb = find(a), find(b)\n",
    "            fa[pb] = pa\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, col in enumerate(row):\n",
    "                idx = 4 * (i * n + j)\n",
    "                #print(i, j, idx)\n",
    "                a, b, c, d = idx, idx + 1, idx + 2, idx + 3\n",
    "                if col == '/':\n",
    "                    #print(a, b, c, d)\n",
    "                    union(a, d)\n",
    "                    union(b, c)\n",
    "                elif col == '\\\\':\n",
    "                    union(a, b)\n",
    "                    union(c, d)\n",
    "                else:\n",
    "                    union(b, a)\n",
    "                    union(c, b)\n",
    "                    union(b, d)\n",
    "                if j + 1 < n:\n",
    "                    #print(b, 4 * (i * n + j + 1) + 3)\n",
    "                    union(b, 4 * (i * n + j + 1) + 3)\n",
    "                if i + 1 < n:\n",
    "                    #print(c, c + 4 * ((i + 1) * n + j))\n",
    "                    union(c,  4 * ((i + 1) * n + j))\n",
    "        for i in range(N):\n",
    "            if i == fa[i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        parent, cnt = list(range(4*n*n)), 4*n*n\n",
    "\n",
    "        def find(p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent[p])\n",
    "            return parent[p]\n",
    "        \n",
    "        def union(p, q):\n",
    "            nonlocal cnt\n",
    "            pRoot = find(p)\n",
    "            qRoot = find(q)\n",
    "            if pRoot != qRoot:\n",
    "                parent[pRoot] = qRoot\n",
    "                cnt -= 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j] == '/':\n",
    "                    union(4*k, 4*k+1)\n",
    "                    union(4*k+2, 4*k+3)\n",
    "                elif grid[i][j] == '\\\\':\n",
    "                    union(4*k, 4*k+3)\n",
    "                    union(4*k+1, 4*k+2)\n",
    "                else:\n",
    "                    union(4*k, 4*k+1)\n",
    "                    union(4*k+1, 4*k+2)\n",
    "                    union(4*k+2, 4*k+3)\n",
    "                if i - 1 >= 0:\n",
    "                    union(4*k+1, 4*((i-1)*n+j)+3)\n",
    "                if j - 1 >= 0:\n",
    "                    union(4*k, 4*(i*n+j-1)+2)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, nxt=None, top=None):\n",
    "        self.val = val\n",
    "        self.next = nxt\n",
    "        self.top = top\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        self.node_list = {}\n",
    "        self.top_node = set()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "          \n",
    "            \n",
    "            for j in range(n):\n",
    "                #if i == 1 and j == 1:\n",
    "                #    break\n",
    "                # 针对每一个格子都有四个小格子\n",
    "                self.init_node(i, j)\n",
    "                if grid[i][j] == '/':\n",
    "                    # 自己合并\n",
    "                    self.merge(self.node_list[(i,j,0)], self.node_list[(i,j,1)])\n",
    "                    self.merge(self.node_list[(i,j,2)], self.node_list[(i,j,3)])\n",
    "                    # 和左合并\n",
    "                    if j - 1 >= 0:\n",
    "                        self.merge(self.node_list[i, j - 1, 3], self.node_list[i, j, 1])\n",
    "                     \n",
    "                    if i - 1 >= 0:\n",
    "                        self.merge(self.node_list[i - 1, j, 2], self.node_list[i, j, 0])\n",
    "                elif grid[i][j] == \"\\\\\":\n",
    "                    self.merge(self.node_list[(i,j,1)], self.node_list[(i,j,2)])\n",
    "                    self.merge(self.node_list[(i,j,0)], self.node_list[(i,j,3)])\n",
    "\n",
    "                    if j - 1 >= 0:\n",
    "                        self.merge(self.node_list[i, j - 1, 3], self.node_list[i, j, 1])\n",
    "                    if i - 1 >= 0:\n",
    "                        self.merge(self.node_list[i - 1, j, 2], self.node_list[i, j, 0])\n",
    "                else:\n",
    "                    self.merge(self.node_list[(i,j,0)], self.node_list[(i,j,3)])\n",
    "                    self.merge(self.node_list[(i,j,1)], self.node_list[(i,j,3)])\n",
    "                    self.merge(self.node_list[(i,j,2)], self.node_list[(i,j,3)])\n",
    "\n",
    "                    if j - 1 >= 0:\n",
    "                        self.merge(self.node_list[i, j - 1, 3], self.node_list[i, j, 1])\n",
    "                    if i - 1 >= 0:\n",
    "                        self.merge(self.node_list[i - 1, j, 2], self.node_list[i, j, 0])\n",
    "\n",
    "        #print([[n.val, n.next.val, n.top.val] for n in self.node_list.values()])\n",
    "        #print(\"\\n\")\n",
    "        #print([s.val for s in self.top_node])\n",
    "        return len(set(self.top_node))\n",
    "\n",
    "\n",
    "    def init_node(self, i, j):\n",
    "        for k in range(4):        \n",
    "            s_node = Node((i, j, k))\n",
    "            s_node.next = s_node\n",
    "            s_node.top = s_node\n",
    "            self.top_node.add(s_node)\n",
    "            self.node_list[(i, j, k)] = s_node\n",
    "\n",
    "\n",
    "\n",
    "    def merge(self, node_x : Node, node_y: Node):\n",
    "        while node_x.top != node_x:\n",
    "            if node_x.top in self.top_node:\n",
    "                self.top_node.remove(node_x.top)\n",
    "            node_x.top = node_y.top\n",
    "            node_x = node_x.next\n",
    "        if node_x.top in self.top_node:\n",
    "            self.top_node.remove(node_x.top)\n",
    "        node_x.top = node_y.top\n",
    "        node_x.next = node_x.top\n",
    "        self.top_node.add(node_x.top)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        def choose_direct(new_i: int, new_j: int, idx: int) -> None:\n",
    "            if 0 <= new_i < m and 0 <= new_j < n:\n",
    "                if grid[new_i][new_j] == ' ':\n",
    "                    dfs(new_i, new_j, 0)\n",
    "                elif grid[new_i][new_j] == '\\\\':\n",
    "                    if idx == 0:\n",
    "                        dfs(new_i, new_j, 4)\n",
    "                    elif idx == 1:\n",
    "                        dfs(new_i, new_j, 4)\n",
    "                    elif idx == 2:\n",
    "                        dfs(new_i, new_j, 1)\n",
    "                    else:\n",
    "                        dfs(new_i, new_j, 1)\n",
    "                else:\n",
    "                    if idx == 0:\n",
    "                        dfs(new_i, new_j, 2)\n",
    "                    elif idx == 1:\n",
    "                        dfs(new_i, new_j, 3)\n",
    "                    elif idx == 2:\n",
    "                        dfs(new_i, new_j, 3)\n",
    "                    else:\n",
    "                        dfs(new_i, new_j, 2)\n",
    "\n",
    "        def dfs(i: int, j: int, d: int) -> None:\n",
    "            if visited[i][j] > 0 and visited[i][j] == d or visited[i][j] == 5:\n",
    "                return\n",
    "            if d == 0:\n",
    "                visited[i][j] = 5\n",
    "            else:\n",
    "                visited[i][j] += d\n",
    "            if d == 0:\n",
    "                for idx, (di, dj) in enumerate(directions):\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    choose_direct(new_i, new_j, idx)\n",
    "            elif d == 1:\n",
    "                for idx, (di, dj) in enumerate(directions[ : 2]):\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    choose_direct(new_i, new_j, idx)\n",
    "            elif d == 2:\n",
    "                for idx in range(1, 3):\n",
    "                    di, dj = directions[idx]\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    choose_direct(new_i, new_j, idx)\n",
    "            elif d == 3:\n",
    "                for idx in [0, 3]:\n",
    "                    di, dj = directions[idx]\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    choose_direct(new_i, new_j, idx)\n",
    "            else:\n",
    "                for idx in range(2, 4):\n",
    "                    di, dj = directions[idx]\n",
    "                    new_i, new_j = i + di, j + dj\n",
    "                    choose_direct(new_i, new_j, idx)\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 5:\n",
    "                    continue\n",
    "                ans += 1\n",
    "                if visited[i][j] == 0:\n",
    "                    if grid[i][j] == '\\\\':\n",
    "                        dfs(i, j, 1)\n",
    "                        if visited[i][j] == 5:\n",
    "                            continue\n",
    "                        ans += 1\n",
    "                        dfs(i, j, 4)\n",
    "                    elif grid[i][j] == '/':\n",
    "                        dfs(i, j, 2)\n",
    "                        if visited[i][j] == 5:\n",
    "                            continue\n",
    "                        ans += 1\n",
    "                        dfs(i, j, 3)\n",
    "                    else:\n",
    "                        dfs(i, j, 0)\n",
    "                else:\n",
    "                    dfs(i, j, 5 - visited[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        parent, cnt = list(range(4*n*n)), 4*n*n\n",
    "\n",
    "        def find(p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent[p])\n",
    "            return parent[p]\n",
    "        \n",
    "        def union(p, q):\n",
    "            nonlocal cnt\n",
    "            pRoot = find(p)\n",
    "            qRoot = find(q)\n",
    "            if pRoot != qRoot:\n",
    "                parent[pRoot] = qRoot\n",
    "                cnt -= 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j] == '/':\n",
    "                    union(4*k, 4*k+1)\n",
    "                    union(4*k+2, 4*k+3)\n",
    "                elif grid[i][j] == '\\\\':\n",
    "                    union(4*k, 4*k+3)\n",
    "                    union(4*k+1, 4*k+2)\n",
    "                else:\n",
    "                    union(4*k, 4*k+1)\n",
    "                    union(4*k+1, 4*k+2)\n",
    "                    union(4*k+2, 4*k+3)\n",
    "                if i - 1 >= 0:\n",
    "                    union(4*k+1, 4*((i-1)*n+j)+3)\n",
    "                if j - 1 >= 0:\n",
    "                    union(4*k, 4*(i*n+j-1)+2)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        \n",
    "        matrix = [[0 for _ in range( 3 * n)] for _ in range(3 * n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '\\\\':\n",
    "                    matrix[i * 3][j * 3] = 1\n",
    "                    matrix[i * 3 + 1][j * 3 + 1] = 1\n",
    "                    matrix[i * 3 + 2][j * 3 + 2] = 1\n",
    "                elif grid[i][j] == '/':\n",
    "                    matrix[i * 3][j * 3 + 2] = 1\n",
    "                    matrix[i * 3 + 1][j * 3 + 1] = 1\n",
    "                    matrix[i * 3 + 2][j * 3] = 1\n",
    "        \n",
    "        count = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix)):\n",
    "                if matrix[i][j] == 0:\n",
    "                    self.dfs(matrix, i, j)\n",
    "                    count += 1\n",
    "        return count\n",
    "    \n",
    "    def dfs(self, matrix, i, j):\n",
    "        if not 0 <= i < len(matrix) or not 0 <= j < len(matrix):\n",
    "            return\n",
    "        \n",
    "        if matrix[i][j] == 1:\n",
    "            return\n",
    "        matrix[i][j] = 1\n",
    "\n",
    "        self.dfs(matrix, i + 1, j)\n",
    "        self.dfs(matrix, i - 1, j)\n",
    "        self.dfs(matrix, i, j + 1)\n",
    "        self.dfs(matrix, i, j - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        parents = [i for i in range(n*n*4)]\n",
    "        def find(x):\n",
    "            parent = parents[x]\n",
    "            while parent != x:\n",
    "                return find(parent)\n",
    "            return parent\n",
    "        def union(x,y):\n",
    "            parents[find(x)] = find(y)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                c = grid[i][j]\n",
    "                base = 4*(i*n+j)\n",
    "                if c == \"/\":\n",
    "                    union(base,base+1)\n",
    "                    union(base+2,base+3)\n",
    "                elif c == \" \":\n",
    "                    union(base,base+1)\n",
    "                    union(base,base+2)\n",
    "                    union(base,base+3)\n",
    "                else:\n",
    "                    union(base,base+3)\n",
    "                    union(base+1,base+2)\n",
    "                if i >= 1:\n",
    "                    union(base+1,4*((i-1)*n+j)+3)\n",
    "                if j >= 1:\n",
    "                    union(base,4*(i*n+j-1)+2)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n*n*4):\n",
    "            if parents[i] == i:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        N = len(grid)\n",
    "        parent = [i for i in range(4*N*N)]\n",
    "\n",
    "        def find(node):\n",
    "            if parent[node]==node:\n",
    "                return node\n",
    "            else:\n",
    "                parent[node]=find(parent[node])\n",
    "                return parent[node]\n",
    "\n",
    "        def union(a,b):\n",
    "            root_a,root_b = find(a),find(b)\n",
    "            if root_a != root_b:\n",
    "                parent[root_a] = root_b\n",
    "\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                base = 4 * (r * N + c)\n",
    "                char = grid[r][c]\n",
    "                # 根据三种不同情况链接四个子块\n",
    "                if char == '\\\\':\n",
    "                    union(base + 0,base + 3)\n",
    "                    union(base + 1,base + 2)\n",
    "                elif char == '/':\n",
    "                    union(base + 0,base + 1)\n",
    "                    union(base + 2,base + 3)\n",
    "                else:\n",
    "                    union(base + 0,base + 1)\n",
    "                    union(base + 2,base + 3)\n",
    "                    union(base + 0,base + 2)\n",
    "                # 若该快右边/下面还有块则连接相应子块\n",
    "                if c < N-1: union(base + 2,base + 4)\n",
    "                if r < N-1: union(base + 3,base + 4*N + 1)\n",
    "        return sum(parent[i] == i for i in range(4*N*N))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        N = n * n * 4\n",
    "        cnt = N\n",
    "\n",
    "        parents = list(range(N))\n",
    "\n",
    "        def find(x):\n",
    "            if x != parents[x]:\n",
    "                parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "        \n",
    "        def union(u,v):\n",
    "            nonlocal cnt\n",
    "            x , y = find(u) , find(v)\n",
    "            if x != y:\n",
    "                parents[x] = y\n",
    "                cnt -= 1\n",
    "\n",
    "        def getPos(i,j,k):\n",
    "            return (i * n + j) * 4 + k\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i > 0:\n",
    "                    union(getPos(i-1,j,3),getPos(i,j,1))\n",
    "                if j > 0:\n",
    "                    union(getPos(i,j-1,2),getPos(i,j,0))\n",
    "                if grid[i][j] == '/':\n",
    "                    union(getPos(i,j,0),getPos(i,j,1))\n",
    "                    union(getPos(i,j,2),getPos(i,j,3))\n",
    "                if grid[i][j] == '\\\\':\n",
    "                    union(getPos(i,j,0),getPos(i,j,3))\n",
    "                    union(getPos(i,j,2),getPos(i,j,1))\n",
    "                if grid[i][j] == ' ':\n",
    "                    union(getPos(i,j,0),getPos(i,j,1))\n",
    "                    union(getPos(i,j,0),getPos(i,j,2))\n",
    "                    union(getPos(i,j,0),getPos(i,j,3))\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        N = len(grid)\n",
    "        parent = [i for i in range(4*N*N)]\n",
    "\n",
    "        def find(node):\n",
    "            if parent[node]==node:\n",
    "                return node\n",
    "            else:\n",
    "                parent[node]=find(parent[node])\n",
    "                return parent[node]\n",
    "\n",
    "        def union(a,b):\n",
    "            root_a,root_b = find(a),find(b)\n",
    "            if root_a != root_b:\n",
    "                parent[root_a] = root_b\n",
    "\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                base = 4 * (r * N + c)\n",
    "                char = grid[r][c]\n",
    "                # 根据三种不同情况链接四个子块\n",
    "                if char == '\\\\':\n",
    "                    union(base + 0,base + 3)\n",
    "                    union(base + 1,base + 2)\n",
    "                elif char == '/':\n",
    "                    union(base + 0,base + 1)\n",
    "                    union(base + 2,base + 3)\n",
    "                else:\n",
    "                    union(base + 0,base + 1)\n",
    "                    union(base + 2,base + 3)\n",
    "                    union(base + 0,base + 2)\n",
    "                # 若该快右边/下面还有块则连接相应子块\n",
    "                if c < N-1: union(base + 2,base + 4)\n",
    "                if r < N-1: union(base + 3,base + 4*N + 1)\n",
    "        return sum(parent[i] == i for i in range(4*N*N))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        m=len(grid)*len(grid)*4\n",
    "        graph=[i for i in range(m)]\n",
    "        def find(nk):\n",
    "            if graph[nk]!=nk:\n",
    "                graph[nk]=find(graph[nk])\n",
    "            return graph[nk]\n",
    "        def union(a,b):\n",
    "            ra,rb=find(a),find(b)\n",
    "            if ra!=rb:\n",
    "                graph[ra]=rb\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                loc=4*(i*len(grid)+j)\n",
    "                b=grid[i][j]\n",
    "                if b==\"/\":\n",
    "                    union(loc+0,loc+1)\n",
    "                    union(loc+2,loc+3)\n",
    "                elif b==\"\\\\\":\n",
    "                    union(loc+3,loc+0)\n",
    "                    union(loc+1,loc+2)\n",
    "                else:\n",
    "                    union(loc+3,loc+0)\n",
    "                    union(loc+1,loc+2)\n",
    "                    union(loc+0,loc+2)\n",
    "                if j<len(grid)-1:\n",
    "                    union(loc+2,loc+4)\n",
    "                if i<len(grid)-1:\n",
    "                    union(loc+3,loc+4*len(grid)+1)\n",
    "        res=0\n",
    "        for k in range(len(graph)):\n",
    "            if graph[k]==k:\n",
    "                res+=1\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n, drcs = len(grid), [[0, 1], [-1, 0], [0, -1], [1, 0]]\n",
    "        visited = [[[0, 0, 0, 0] for _ in range(n)] for _ in range(n)]\n",
    "        drcs = [[0, -1, 2, 1, 3], [1, 0, 3, 0, 2], [0, 1, 0, 3, 1], [-1, 0, 1, 2, 0]]\n",
    "        def dfs(r, c, k):\n",
    "            visited[r][c][k] = ans\n",
    "            nr, nc, p0, p1, p2 = r + drcs[k][0], c + drcs[k][1], drcs[k][2], drcs[k][3], drcs[k][4]\n",
    "            if -1 < nr < n and -1 < nc < n and visited[nr][nc][p0] == 0:\n",
    "                dfs(nr, nc, p0)\n",
    "            if grid[r][c] != '/' and visited[r][c][p1] == 0: dfs(r, c, p1)\n",
    "            if grid[r][c] != '\\\\' and visited[r][c][p2] == 0: dfs(r, c, p2)\n",
    "        ans = 0\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                for k in range(4):\n",
    "                    if visited[r][c][k] == 0:\n",
    "                        ans += 1\n",
    "                        dfs(r, c, k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        m=len(grid)*len(grid)*4\n",
    "        graph=[i for i in range(m)]\n",
    "        def find(nk):\n",
    "            if graph[nk]!=nk:\n",
    "                graph[nk]=find(graph[nk])\n",
    "            return graph[nk]\n",
    "        def union(a,b):\n",
    "            ra,rb=find(a),find(b)\n",
    "            if ra!=rb:\n",
    "                graph[ra]=rb\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                loc=4*(i*len(grid)+j)\n",
    "                b=grid[i][j]\n",
    "                if b==\"/\":\n",
    "                    union(loc+0,loc+1)\n",
    "                    union(loc+2,loc+3)\n",
    "                elif b==\"\\\\\":\n",
    "                    union(loc+3,loc+0)\n",
    "                    union(loc+1,loc+2)\n",
    "                else:\n",
    "                    union(loc+3,loc+0)\n",
    "                    union(loc+1,loc+2)\n",
    "                    union(loc+0,loc+2)\n",
    "                if j<len(grid)-1:\n",
    "                    union(loc+2,loc+4)\n",
    "                if i<len(grid)-1:\n",
    "                    union(loc+3,loc+4*len(grid)+1)\n",
    "        res=0\n",
    "        for k in range(len(graph)):\n",
    "            if graph[k]==k:\n",
    "                res+=1\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        \n",
    "        count = 4 * n * n\n",
    "        parent = list(range(4 * n * n))\n",
    "\n",
    "        def union(x, y):\n",
    "            nonlocal count\n",
    "            rootX = find(x)\n",
    "            rootY = find(y)\n",
    "            if rootX == rootY:\n",
    "                return\n",
    "            parent[rootX] = rootY\n",
    "            count -= 1\n",
    "\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                index = 4 * (i * n + j)\n",
    "                if grid[i][j] == '/':\n",
    "                    union(index, index + 3)\n",
    "                    union(index + 1, index + 2)\n",
    "                elif grid[i][j] == '\\\\':\n",
    "                    union(index, index + 1)\n",
    "                    union(index + 2, index + 3)\n",
    "                else:\n",
    "                    union(index, index + 1)\n",
    "                    union(index + 1, index + 2)\n",
    "                    union(index + 2, index + 3)\n",
    "\n",
    "                if j + 1 < n:\n",
    "                    union(index + 1, 4 * (i * n + j + 1) + 3)\n",
    "                if i + 1 < n:\n",
    "                    union(index + 2, 4 * ((i + 1) * n + j))\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        mat = [[0 for _ in range(n * 3)] for _ in range(n * 3)]\n",
    "\n",
    "        def change(x, y, key):\n",
    "            if key == '/':\n",
    "                mat[3 * x][3 * y + 2] = 1\n",
    "                mat[3 * x + 1][3 * y + 1] = 1\n",
    "                mat[3 * x + 2][3 * y] = 1\n",
    "            elif key == '\\\\':\n",
    "                mat[3 * x][3 * y] = 1\n",
    "                mat[3 * x + 1][3 * y + 1] = 1\n",
    "                mat[3 * x + 2][3 * y + 2] = 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                change(i, j, grid[i][j])\n",
    "        \n",
    "        ans = 0\n",
    "        aspect = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        def dfs(x, y):\n",
    "            mat[x][y] = 1\n",
    "            for a, b in aspect:\n",
    "                a += x\n",
    "                b += y\n",
    "                if 0 <= a < 3 * n and 0 <= b < 3 * n and mat[a][b] == 0:\n",
    "                    dfs(a, b)\n",
    "        \n",
    "        for i in range(3 * n):\n",
    "            for j in range(3 * n):\n",
    "                if not mat[i][j]:\n",
    "                    dfs(i, j)\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        mat = [[0 for _ in range(n * 3)] for _ in range(n * 3)]\n",
    "\n",
    "        def change(x, y, key):\n",
    "            if key == '/':\n",
    "                mat[3 * x][3 * y + 2] = 1\n",
    "                mat[3 * x + 1][3 * y + 1] = 1\n",
    "                mat[3 * x + 2][3 * y] = 1\n",
    "            elif key == '\\\\':\n",
    "                mat[3 * x][3 * y] = 1\n",
    "                mat[3 * x + 1][3 * y + 1] = 1\n",
    "                mat[3 * x + 2][3 * y + 2] = 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                change(i, j, grid[i][j])\n",
    "        \n",
    "        ans = 0\n",
    "        aspect = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        def dfs(x, y):\n",
    "            mat[x][y] = 1\n",
    "            for a, b in aspect:\n",
    "                a += x\n",
    "                b += y\n",
    "                if 0 <= a < 3 * n and 0 <= b < 3 * n and mat[a][b] == 0:\n",
    "                    dfs(a, b)\n",
    "        \n",
    "        for i in range(3 * n):\n",
    "            for j in range(3 * n):\n",
    "                if not mat[i][j]:\n",
    "                    dfs(i, j)\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def regionsBySlashes(self, grid: List[str]) -> int:\n",
    "        boss = collections.defaultdict(lambda: None)\n",
    "        def find(x):\n",
    "            if boss[x]==None:return x\n",
    "            else:\n",
    "                boss[x]=find(boss[x])\n",
    "                return boss[x]\n",
    "        def join(a,b):\n",
    "            A, B = find(a), find(b)\n",
    "            if A!=B:\n",
    "                boss[A]=B\n",
    "        N,M = len(grid), len(grid[0])\n",
    "        for i in range(N):\n",
    "            for j in range(M):\n",
    "                ch = grid[i][j]\n",
    "                if ch != '/':\n",
    "                    join((i,j,0),(i,j,2))\n",
    "                    join((i,j,1),(i,j,3))\n",
    "                if ch != '\\\\':\n",
    "                    join((i,j,0),(i,j,1))\n",
    "                    join((i,j,2),(i,j,3))\n",
    "                join((i,j,0),(i-1,j,3))\n",
    "                join((i,j,1),(i,j-1,2))\n",
    "        return list(boss.values()).count(None)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
